package Hash;

import java.util.HashSet;
import java.util.Iterator;

public class longestConsecutive {
    //暴力解失败，因为数字跨度太广了
    // public static int longestConsecutive(int[] nums) {
    //     if (nums.length==0) {
    //         return 0;
    //     }else if (nums.length==1) {
    //         return 1;
    //     }
    //     //有正有负且无序
    //     //空间换时间
    //     //先找到min和max，确定数组的大小
    //     //爆内存了，[0,1,2,4,8,5,6,7,9,3,55,88,77,99,999999999]
    //     int min=0,max=0;
    //     for(int i=0;i<nums.length;i++){
    //         min=Math.min(min, nums[i]);
    //         max=Math.max(max, nums[i]);
    //     }
    //     boolean [] arr = new boolean[max-min+1];
    //     for(int i=0;i<nums.length;i++){
    //         //因为有正有负，因此index做映射
    //         int index = nums[i]-min;
    //         if (!arr[index]) {
    //             //完成初始化   
    //             arr[index]=true;
    //         }
    //     }
    //     int count = 1,temp=1;
        
    //     for(int i=1;i<arr.length;i++){
    //         if (arr[i]&&arr[i-1]) {
    //             temp++;
    //         }else{
    //             count=Math.max(count, temp);
    //             temp=1;
    //         }
            
    //     }
    //     return Math.max(count,temp);
    // }
    //使用hashset+containValue
    public static int longestConsecutive(int[] nums) {
        //考虑为空的情况
        if (nums.length==0) {
            return 0;
        }
        //首先结果存放在hashset去重
        HashSet<Integer> set = new HashSet<>(nums.length);
        for(int num: nums){
            if (!set.contains(num)) {
                set.add(num);
            }
        }
        //遍历set
       Iterator<Integer> iterator = set.iterator();
       int count=1,temp=1;
       while (iterator.hasNext()) {
            Integer nextNum = iterator.next();
            temp=1;
            //对于一个值，先找他的最小值
            if (!set.contains(nextNum-1)) {
                //当前值为连续数中最小值，找他连续的个数
                while (set.contains(nextNum+1)) {
                    temp++;
                    nextNum++;
                }
                count=Math.max(count, temp);
            }
       }
       return count;
    }
    public static void main(String[] args) {
        // int[] nums = new int[]{0,3,7,2,5,8,4,6,0,1};
        // int[] nums = new int[]{100,4,200,1,3,2};
        // int[] nums = new int[]{100,4,200,-1,-3,-2};
        int[] nums = new int[]{0,1,2,4,8,5,6,7,9,3,55,88,77,99,999999999};
        int length = longestConsecutive(nums);
        System.out.println(length);
    }
}
